package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author c2b
 * @since 2025/2/13 16:10
 */
public class LC0051NQueens_H {


    static class Solution {
        public List<List<String>> solveNQueens(int n) {
            char[][] chessboard = new char[n][n];
            for (char[] c : chessboard) {
                Arrays.fill(c, '.');
            }
            List<List<String>> resList = new ArrayList<>();
            backtracking(n, 0, chessboard, resList);
            return resList;
        }

        /**
         * backtracking 保证了从上到下，行的增加。for循环保证了从左到右，列的增加。
         * check方法用来校验不同行、不同列、不同斜线。
         */
        private void backtracking(int n, int row, char[][] chessboard, List<List<String>> resList) {
            if (row == n) {
                List<String> path = new ArrayList<>();
                for (char[] chars : chessboard) {
                    path.add(new String(chars));
                }
                resList.add(path);
                return;
            }
            // ++col：进入下一列
            for (int col = 0; col < n; ++col) {
                if (check(n, chessboard, row, col)) {
                    chessboard[row][col] = 'Q';     // 处理
                    backtracking(n, row + 1, chessboard, resList);  // 进入下一行
                    chessboard[row][col] = '.';     // 回溯
                }
            }
        }

        private boolean check(int n, char[][] chessboard, int row, int col) {
            int[][] d = new int[][]{{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
            // 检查列，同一列的不同行不允许有重复
            for (int i = 0; i < row; ++i) { // 相当于剪枝
                if (chessboard[i][col] == 'Q') {
                    return false;
                }
            }
            // 检查行，同一行的不同列不允许有重复
            for (int i = 0; i < col; i++) {
                if (chessboard[row][i] == 'Q') {
                    return false;
                }
            }
            // 检查45度对角线
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                if (chessboard[i][j] == 'Q') {
                    return false;
                }
            }
            // 检查135度对角线
            for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
                if (chessboard[i][j] == 'Q') {
                    return false;
                }
            }
            return true;
        }

        public List<List<String>> solveNQueens2(int n) {
            boolean[] usedCols = new boolean[n];
            boolean[] used045 = new boolean[2 * n];
            boolean[] used135 = new boolean[2 * n];
            List<List<String>> resList = new ArrayList<>();
            char[][] chessboard = new char[n][n];
            for (char[] c : chessboard) {
                Arrays.fill(c, '.');
            }
            backtracking(n, 0, chessboard, usedCols, used045, used135, resList);
            return resList;
        }

        private void backtracking(int n, int row, char[][] chessboard, boolean[] usedCols, boolean[] used045, boolean[] used135, List<List<String>> resList) {
            if (row == n) {
                List<String> path = new ArrayList<>();
                for (char[] chars : chessboard) {
                    path.add(new String(chars));
                }
                resList.add(path);
                return;
            }
            for (int col = 0; col < n; col++) {
                /*
                主对角线: col-row+n         副对角线: row + col
                     0   1   2   3               0   1   2   3
                    ---------------             ---------------
                 0 | 4 | 5 | 6 | 7 |         0 | 0 | 1 | 2 | 3 |
                 1 | 3 | 4 | 5 | 6 |         1 | 1 | 2 | 3 | 4 |
                 2 | 2 | 3 | 4 | 5 |         2 | 2 | 3 | 4 | 5 |
                 3 | 1 | 2 | 3 | 4 |         3 | 3 | 4 | 5 | 6 |
                    ---------------             ---------------
                 */
                int zdjIdx = col - row + n; // 主对角线的索引
                int fdjIdx = col + row;     // 副对角线的索引
                // backtracking方法保证了不同行，只需校验不同列、不同对角线
                if (!usedCols[col] && !used045[zdjIdx] && !used135[fdjIdx]) {
                    // 处理
                    chessboard[row][col] = 'Q';
                    usedCols[col] = used045[zdjIdx] = used135[fdjIdx] = true;
                    // 递归
                    backtracking(n, row + 1, chessboard, usedCols, used045, used135, resList);
                    // 回溯
                    chessboard[row][col] = '.';
                    usedCols[col] = used045[zdjIdx] = used135[fdjIdx] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (int i = 1; i < 9; i++) {
            Printer.printListListString(solution.solveNQueens(i));
        }
    }

}
